package study.datastructure.queue.impl;

import java.util.Arrays;

/**
 * 大顶堆 实现 优先级队列 插入删除操作都是log(n)
 * @author 86188
 */
public class MaxHeapPriorityQueue {
    private int[] heap;       // 存储堆元素的数组
    private int size;          // 当前堆中的元素数量
    private int capacity;      // 堆的容量

    // 构造函数初始化堆容量
    public MaxHeapPriorityQueue(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // 获取父节点索引
    private int parent(int i) { return (i - 1) / 2; }

    // 获取左子节点索引
    private int leftChild(int i) { return 2 * i + 1; }

    // 获取右子节点索引
    private int rightChild(int i) { return 2 * i + 2; }

    // 向优先级队列中插入元素
    public void insert(int element) {
        validFull(capacity, "Heap is full");
        heap[size++] = element;
        heapifyUp(size - 1);
    }

    private void validFull(int capacity, String Heap_is_full) {
        if (size == capacity) {
            throw new IllegalStateException(Heap_is_full);
        }
    }

    // 删除并返回堆顶（最大值）元素
    public int extractMax() {
        validFull(0, "Heap is empty");
        int max = heap[0];
        heap[0] = heap[--size];
        heapifyDown(0);
        return max;
    }

    // 获取堆顶元素（最大值）
    public int peek() {
        validFull(0, "Heap is empty");
        return heap[0];
    }

    // 上浮操作：维持堆结构
    private void heapifyUp(int i) {
        int parent= parent(i);
        while (i > 0 && heap[parent] < heap[i]) {
            swap(i, parent(i));
            i = parent;
            parent = parent(i);
        }
    }

    // 下沉操作：维持堆结构
    private void heapifyDown(int parent) {
        int largest = parent;
        int left = leftChild(parent);
        int right = left+1;

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != parent) {
            swap(parent, largest); //交换父节点和最大子节点 根据索引
            heapifyDown(largest);
        }
    }

    // 交换两个元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 打印堆元素
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOf(heap, size)));
    }

    public static void main(String[] args) {
        MaxHeapPriorityQueue maxHeap = new MaxHeapPriorityQueue(10);
        maxHeap.insert(3);
        maxHeap.insert(5);
        maxHeap.insert(9);
        maxHeap.insert(1);
        maxHeap.insert(10);

        System.out.println("Heap elements after insertion:");
        maxHeap.printHeap();

        System.out.println("Extracted max: " + maxHeap.extractMax());
        System.out.println("Heap after extracting max:");
        maxHeap.printHeap();
    }
}
